Maximum Inner Product Search (MIPS) is an important task in many machine learning applications such as the prediction phase of low-rank matrix factorization models and deep learning models. Recently, there has been substantial research on how to perform MIPS in sub-linear time, but most of the existing work does not have the flexibility to control the trade-off between search efficiency and search quality. In this paper, we study the important problem of MIPS with a computational budget. By carefully studying the problem structure of MIPS, we develop a novel Greedy-MIPS algorithm, which can handle budgeted MIPS by design. While simple and intuitive, Greedy-MIPS yields surprisingly superior performance compared to state-of-the-art approaches. As a specific example, on a candidate set containing half a million vectors of dimension 200, Greedy-MIPS runs 200x faster than the naive approach while yielding search results with the top-5 precision greater than 75%.

It should read "unions" of subspaces. Thank you for pointing out the typo.

Learning reduced models from data in a nonintrusive fashion is an important problem in science and engineering [1, 2, 3]. A typical approach is to first learn an encoder-decoder pair, embed the training snapshot trajectories with the learned encoder, and then fit a reduced dynamical-system model to the embedded trajectories. However, the decomposition of the training process into first learning an encoder-decoder pair for the embedding and only sub-sequentially learning a model of the dynamics typically means that the encoder-decoder pair are trained with the objective of accurately approximating the training data, rather than taking the reduced-model prediction error into account. Thus, the encoder-decoder pair can overfit to achieving a low reconstruction error on the training data by learning embeddings of the snapshot trajectories that are non-smooth, which means that learning a reduced model can become challenging. Correspondingly, it has been observed that learning embeddings and models together can be beneficial; see, e.g., [4, 5, 6, 7]. In the context of intrusive model reduction with linear approximations, there is work that optimizes the reduced basis with respect to the model prediction error [8], quantities of interest [9], and to achieve stability [10]; however, we focus here on the setting of nonintrusive model reduction and nonlinear approximations.

--The advent of accessible Generative AI tools enables anyone to create and spread synthetic images on social media, often with the intention to mislead, thus posing a significant threat to online information integrity. Most existing Synthetic Image Detection (SID) solutions struggle on generated images sourced from the Internet, as these are often altered by compression and other operations. T o address this, our research enhances SID by exploring data augmentation combinations, leveraging a genetic algorithm for optimal augmentation selection, and introducing a dual-criteria optimization approach. These methods significantly improve model performance under real-world perturbations. Our findings provide valuable insights for developing detection models capable of identifying synthetic images across varying qualities and transformations, with the best-performing model achieving a mean average precision increase of +22.53% compared to models without augmentations.

The aim of the paper is to propose a new greedy approach for Maximum Inner Product Search problem: given a candidate vector, retrieve a set of vectors with maximum inner product to the query vector. This is a crucial step in several machine learning and data mining algorithms, and the state of the art methods work in sub-linear time recently. The originality of the paper is to study the MIPS problem under a computational budget. The proposed approach achieves better balance between search efficiency and quality of the retrieved vectors, and does not require a nearest neighbor search phase, as commonly done by state of the art approaches. The authors claim impressive runtime results (their algorithm is 200x faster than the naive approach), and a top-5 precision greater than 75%.

In real-world applications, users often favor structurally diverse design choices over one high-quality solution. It is hence important to consider more solutions that decision-makers can compare and further explore based on additional criteria. Alongside the existing approaches of evolutionary diversity optimization, quality diversity, and multimodal optimization, this paper presents a fresh perspective on this challenge by considering the problem of identifying a fixed number of solutions with a pairwise distance above a specified threshold while maximizing their average quality. We obtain first insight into these objectives by performing a subset selection on the search trajectories of different well-established search heuristics, whether specifically designed with diversity in mind or not. We emphasize that the main goal of our work is not to present a new algorithm but to look at the problem in a more fundamental and theoretically tractable way by asking the question: What trade-off exists between the minimum distance within batches of solutions and the average quality of their fitness? These insights also provide us with a way of making general claims concerning the properties of optimization problems that shall be useful in turn for benchmarking algorithms of the approaches enumerated above. A possibly surprising outcome of our empirical study is the observation that naive uniform random sampling establishes a very strong baseline for our problem, hardly ever outperformed by the search trajectories of the considered heuristics. We interpret these results as a motivation to develop algorithms tailored to produce diverse solutions of high average quality.

This work focuses on developing an effective meta-heuristic approach to protect against simultaneous attacks on nodes of a network modeled using a graph. Specifically, we focus on the $k$-strong Roman domination problem, a generalization of the well-known Roman domination problem on graphs. This general problem is about assigning integer weights to nodes that represent the number of field armies stationed at each node in order to satisfy the protection constraints while minimizing the total weights. These constraints concern the protection of a graph against any simultaneous attack consisting of $k \in \mathbb{N}$ nodes. An attack is considered repelled if each node labeled 0 can be defended by borrowing an army from one of its neighboring nodes, ensuring that the neighbor retains at least one army for self-defense. The $k$-SRD problem has practical applications in various areas, such as developing counter-terrorism strategies or managing supply chain disruptions. The solution to this problem is notoriously difficult to find, as even checking the feasibility of the proposed solution requires an exponential number of steps. We propose a variable neighborhood search algorithm in which the feasibility of the solution is checked by introducing the concept of quasi-feasibility, which is realized by careful sampling within the set of all possible attacks. Extensive experimental evaluations show the scalability and robustness of the proposed approach compared to the two exact approaches from the literature. Experiments are conducted with random networks from the literature and newly introduced random wireless networks as well as with real-world networks. A practical application scenario, using real-world networks, involves applying our approach to graphs extracted from GeoJSON files containing geographic features of hundreds of cities or larger regions.

The optimal experimental design (OED) problem arises in numerous settings, with applications ranging from combustion kinetics Huan & Marzouk (2013), sensor placement for weather prediction Krause et al. (2008), containment source identification Attia et al. (2018), to pharmaceutical trials Djuris et al. (2024). A commonly addressed version of the OED problem centers on the fundamental question of selecting an optimal subset of k observations from a total pool of n possible candidates, with the goal of learning the parameters of a statistical model for the observations. In the Bayesian framework, these parameters are endowed with a prior distribution to represent our state of knowledge before seeing the data. A posterior distribution on the parameters is obtained by conditioning on the observations. A commonly used experimental design criterion is then the mutual information (MI) between the parameters and the selected observations or, equivalently, the expected information gain from prior to posterior, which should be maximized.

In modern feedback control systems theory and practice, reliable access to the dynamically evolving system states is needed at both the implementation stage of advanced control algorithms and for process/system condition and performance monitoring purposes [16, 8, 39, 13, 47]. Traditionally, an explicit use of an available dynamic model complemented by sensor measurements, involving measurable physical and chemical variables of the system of interest, represented a first option to respond to the above need. However, in practice, key critical state variables are often not available for direct on-line measurement, due to inherent physical as well as practically insurmountable technical and economic limitations associated with the current state of sensor technology as it is invariably deployed in cases of considerable system complexity [47, 16, 8, 39]. In light of the above remarks, a better, scientifically sound and practically insightful option is the design of a state estimator (an observer). This is itself an appropriately structured dynamical system itself that utilizes all information provided by a system model as well as available sensor measurements to accurately reconstruct the dynamic profiles of all other unmeasurable state variables [47, 16, 8, 13].

We study the problem of selecting a fleet of robots to service spatially distributed tasks with diverse requirements within time-windows. The problem of allocating tasks to a fleet of potentially heterogeneous robots and finding an optimal sequence for each robot is known as multi-robot task assignment (MRTA). Most state-of-the-art methods focus on the problem when the fleet of robots is fixed. In contrast, we consider that we are given a set of available robot types and requested tasks, and need to assemble a fleet that optimally services the tasks while the cost of the fleet remains under a budget limit. We characterize the complexity of the problem and provide a Mixed-Integer Linear Program (MILP) formulation. Due to poor scalability of the MILP, we propose a heuristic solution based on a Large Neighbourhood Search (LNS). In simulations, we demonstrate that the proposed method requires substantially lower budgets than a greedy algorithm to service all tasks.